#include<stdio.h>
#include<iostream>
using namespace std;

//存储结构----记录序列以顺序表存储 
#define InfoType char
#define MAXSIZE 20   //设记录不超过20个
typedef int KeyType; //设关键字为整型量(int 型)
typedef struct{  //定义每个记录(数据元素)的结构  
	KeyType key; //关键字 
	InfoType otherinfo; //其它数据项 
} RedType; //Record Type 
typedef struct{ //定义顺序表的结构 
	RedType r[MAXSIZE + 1]; //存储顺序表的向量  //r[0]一般作为哨兵或缓冲区 
	int length; //顺序表的长度 
}SqList;



//交换排序基本思想: 两两比较, 如果发生逆序则交换, 直到所有记录都排好序为止  


//冒泡排序: O(n2)
//基本思想：每趟不断记录两两比较, 并按"前小后大"规则交换 
void bubble_sort(SqList &L){ //冒泡排序算法 
	int i, j; 
	RedType x; //交换时临时存储
	for(int i = 1; i <= L.length-1; i++){//总共需要 L.length-1 趟 
		for(int j = 1; j <= L.length-i-1; j++){
			if(L.r[j].key > L.r[j+1].key){//发生逆序 
				x = L.r[j];
				L.r[j] = L.r[j+1];
				L.r[j+1] = x;
			}//endif
		}//for
	} 
}


//快速排序: O(nlog2n) ----改进的交换排序
//基本思想：
//(1): 任取一个元素(如：第一个)为中心  pivot: 枢轴、中心点 
//(2): 所有比它小的元素一律前放, 比它大的元素一律放后, 形成左右两个子表  
//(3): 对各子表重新选择中心元素并依此规则调整, 直到每个子表的元素只剩一个 

int Partition(SqList &L, int low, int high){
	L.r[0] = L.r[low];
	int pivotkey = L.r[low].key;
	while(low < high){
		while(low < high && L.r[high].key >= pivotkey) --high;
		L.r[low] = L.r[high];
		while(low < high && L.r[low].key <= pivotkey) ++low;
		L.r[high] = L.r[low];
	}
	L.r[low] = L.r[0];
	return low;
} 


void QSort(SqList &L, int low, int high){ //对顺序表L快速排序
	if(low < high){  //长度大于1  
		int pivotloc = Partition(L, low, high);
		//将L.r[low...high]一分为二, pivotloc为枢轴元素排好序的位置 
		QSort(L, low, pivotloc - 1); //对低字表递归排序
		QSort(L, pivotloc + 1, high); //对高字表递归排序 
	} //endif
}//QSort

int main(void)
{
	return 0;
}